package org.example.GC;

import javax.swing.tree.TreeNode;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class BFS {
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        String startStr = "0000";
        if (set.contains(startStr)) {
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(startStr);
        visited.add(startStr);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                String str = queue.poll();
                for (int i = 0; i < 4; i++) {
                    char ch = str.charAt(i);
                    String strAdd = str.substring(0, i) + (ch == '9' ? 0 : ch - '0' + 1) + str.substring(i + 1);
                    String strSub = str.substring(0, i) + (ch == '0' ? 9 : ch - '0' - 1) + str.substring(i + 1);
                    if (str.equals(target))
                        return level;
                    if (!visited.contains(strAdd) && !set.contains(strAdd)) {
                        queue.offer(strAdd);
                        visited.add(strAdd);
                    }
                    if (!visited.contains(strSub) && !set.contains(strSub)) {
                        queue.offer(strSub);
                        visited.add(strSub);
                    }
                }
            }
            level++;
        }
        return -1;
    }
    public int numSquares(int n) {
       Queue<Integer> queue = new LinkedList<>();
       Set<Integer> visited = new HashSet<>();
       queue.offer(0);
       visited.add(0);
       int level = 0;
       while (!queue.isEmpty()){
           int size = queue.size();
           level++;
           for (int i=0;i<size;i++){
               int digit = queue.poll();
               for (int j =1;j<+n;j++){
                   int nodeValue = digit +j*j;
                   if (nodeValue==n){
                       return level;
                   }
                   if (nodeValue>n){
                       break;
                   }
                   if (!visited.contains(nodeValue)){
                      visited.add(nodeValue);
                      queue.offer(nodeValue);
                   }
               }
           }
       }
       return level;
    }
}
